package com.bruce.algorithm.leetcode;

import java.math.BigInteger;

/**
 * @author luotuan
 * @Description 2数相加
 * @create 2020-07-10 14:42
 **/
public class TwoNumbersSum {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = null;
        String s1 = "";
        String s2 = "";
        while (l1 != null) {
            s1 += l1.val;
            l1 = l1.next;
        }
        while (l2 != null) {
            s2 += l2.val;
            l2 = l2.next;
        }
        BigInteger num1 = new BigInteger(new StringBuffer(s1).reverse().toString());
        BigInteger num2 = new BigInteger(new StringBuffer(s2).reverse().toString());
        BigInteger sum = num1.add(num2);
        String sumStr = new StringBuffer(sum.toString()).reverse().toString();
        char[] chars = sumStr.toCharArray();
        for (char num : chars) {
            int target = num - '0';
            ListNode node = new ListNode(target);
            if (result == null) {
                result = node;
            } else {
                ListNode tmp = result;
                while (true) {
                    if (tmp.next == null) {
                        tmp.next = node;
                        break;
                    }
                    tmp = tmp.next;
                }
            }

        }
        return result;
    }

    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        //结果
        ListNode root = new ListNode(0);
        ListNode current = root;
        int post = 0;
        /**
         *  规律：2链表对应字段相加，如果相加结果大于1，则向后进1，后一位的链表字段相加把1加上，后续重复步骤
         */
        while (l1 != null || l2 != null || post != 0) {
            // 取 2个链表同位置的数字，如果Node为空，则赋值为0
            int num1 = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;
            // 相加
            int sum = num1 + num2 + post;
            // 节点值
            int nodeValue = sum % 10;
            // 是否进1
            post = (sum>=10)?1:0;
            ListNode node = new ListNode(nodeValue);
            current.next = node;
            current = node;
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
        }
        return root.next;
    }

    private static ListNode reverseLinkedList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        ListNode next = null;
        while (head.next != null) {
            next = head.next;   //保存下一个节点
            head.next = prev;   //重置next
            prev = head;    //保存当前节点
            head = next;
        }
        head.next = prev;
        return head;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(6);
        ListNode node6 = new ListNode(4);
        node4.next = node5;
        node5.next = node6;
        ListNode result = addTwoNumbers2(node1, node4);
        while (result != null) {
            System.out.print(result.val + ",");
            result = result.next;
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
